On the number of disjoint perfect matchings of regular graphs with given edge connectivity

Title: On the number of disjoint perfect matchings of regular graphs with given edge connectivity
Creator: Lu, Hongliang; Lin, Yuqing
Relation: Discrete Mathematics Vol. 340, Issue 3, p. 305-310
Publisher Link: http://dx.doi.org/10.1016/j.disc.2016.09.002
Publisher: Elsevier
Resource Type: journal article
Date: 2017
Description: The problem of how many edge disjoint perfect matchings are there in a regular graph has attracted considerable interest. Most of the work focus on the case where the degree is large, roughly speaking, equal to half of the total number of the vertices in the graph. In this paper, we look at the case where the degree is smaller. Let n,k,m be three positive integers such that k=⎣(n - 1)/2⎦ and m≤k, we show that every 2k-regular m-edge-connected graph with 2n vertices contains at least m edge-disjoint perfect matchings, and the condition on edge connectivity is sharp.
Subject: edge disjoint perfect matching; 1-factorization conjecture
Identifier: http://hdl.handle.net/1959.13/1354613
Identifier: uon:31313
Identifier: ISSN:0012-365X
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format